#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

void nextPermutation(vector<int> &nums) {
  int pos = -1;
  for (int i = nums.size() - 2; i >= 0; --i) {
    if (nums[i] < nums[i + 1]) {
      pos = i;
      break;
    }
  }
  // 当前数组为降序排列
  if (pos == -1) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      swap(nums[left++], nums[right--]);
    }
    return;
  }
  // 找到pos后面比nums[pos]大的最小数下标minPos，交换nums[pos]和nums[minPos], 对
  // pos位置之后的数据进行升序排序
  int minPos = -1;
  for (int i = pos + 1; i < nums.size(); ++i) {
    if (minPos == -1 && nums[pos] < nums[i]) {
      minPos = i;
    }
    if (minPos != -1 && nums[pos] < nums[i] && nums[i] < nums[minPos]) {
      minPos = i;
    }
  }
  swap(nums[pos], nums[minPos]);
  sort(nums.begin() + pos + 1, nums.end());
}
